package main

func main() {

}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	return 1 + max(maxDepth(root.Left), maxDepth(root.Right))
}
func max(a, b int) int {
	if a < b {
		return b
	}
	return a
}

/**
 * @Description:给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
*/
func maxDepthByBfs(root *TreeNode) int {
	if root == nil {
		return 0
	}
	result := 0
	queue := new(Queue)
	queue.offer(root)
	for len(queue.nums) > 0 {
		length := len(queue.nums)
		for length > 0 {
			poll := queue.poll()
			if poll.Left != nil {
				queue.offer(poll.Left)
			}
			if poll.Right != nil {
				queue.offer(poll.Right)
			}
			length--
		}
		result++
	}
	return result
}

type Queue struct {
	nums []*TreeNode
}

func (q *Queue) offer(node *TreeNode) {
	if q == nil {
		q.nums = make([]*TreeNode, 0)
	}
	q.nums = append(q.nums, node)
}

func (q *Queue) poll() (node *TreeNode) {
	node = q.nums[0]
	q.nums = q.nums[1:]
	return node
}
